package com.example.algorithm.service.impl;

import com.example.algorithm.service.BinarySearchService;
import org.springframework.stereotype.Service;

import java.util.Arrays;

/** 二分查找法
 * @auth Administrator
 * @create @2024/8/4@21:46
 * @decription
 **/
@Service
public class BinarySearchServiceImpl implements BinarySearchService {
    /**NO.62 搜索插入位置
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * @param nums
     * @param target
     * @return
     * 解法一：二分查找法(区间开闭)
     * 解法二:库函数
     *
     */
    @Override
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length;
        while (left <right){
            int mid = left +(right-left)/2;
            if(target<nums[mid]){
                right = mid;
            }else if(target>nums[mid]){
                left =mid+1;
            }else {
                return mid;
            }
        }
        return right;
    }

    /**NO.63 搜索二维码矩阵
     * 给你一个满足下述两条属性的 m x n 整数矩阵：
     *
     * 每行中的整数从左到右按非严格递增顺序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
     * @param matrix
     * @param target
     * @return
     * 解法一：两次二分查找
     *解法二：一次二分查找
     * 解法三：排除法
     * 解法四：暴力查询
     * 解法五：抽象 BST 解法
     * 解法六：坐标轴
     *
     */
    @Override
    public boolean searchMatrix(int[][] matrix, int target) {
        int xRay = matrix.length;
        int yRay= matrix[0].length;
        int left =0;
        int right = xRay*yRay-1;
        while (left <right){
            int mid = left+(right-left)/2;
            int res = matrix[mid/yRay][mid%yRay];
            if(target>res){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return matrix[left/yRay][left%yRay]==target;
    }

    /**NO.64 在排序数组中查找元素的第一个和最后一个位置
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     *
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     *
     * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
     * @param nums
     * @param target
     * @return
     *
     * 解法一：二分查找(迭代及递归)
     *
     */
    @Override
    public int[] searchRange(int[] nums, int target) {
        int left =0;
        int right =nums.length-1;

        while (left <=right){
            int mid=left+(right-left)/2;
            if(target==nums[mid]){
                left = mid;
                while (left-1>=0&&target==nums[left-1]){
                    --left;
                }
                right=mid;
                while (right+1<nums.length&&target==nums[right+1]){
                    ++right;
                }
                return new int[]{left,right};
            }

            if(target>nums[mid]){
                left = mid+1;
            }else if (target<nums[mid] ){
                right = mid-1;
            }
        }


        return new int[]{-1,-1};
    }

    /**
     * NO.65 搜索旋转排序树组
     * 整数数组 nums 按升序排列，数组中的值 互不相同 。
     *
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
     *
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
     *
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     *
     *
     * @param nums
     * @param target
     * @return
     *
     * 解法一：二分查找法(寻找下标，分2段)
     * 解法二：直接搜索
     *
     */
    @Override
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;

        while (left <=right){
            int mid = (left +right)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]<nums[right]){
                if(nums[mid]<target&&target<=nums[right]){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }else{
                if(nums[mid]>target&&target>=nums[left]){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }

        }
        return -1;

    }

    /**NO.66 寻找旋转排序数组中的最小值
     * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
     * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
     * 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
     * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     *
     * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
     *
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     * @param nums
     * @return
     * 解法一：二分查找
     *
     */
    @Override
    public int findMin(int[] nums) {
        int left=0;
        int right=nums.length-1;
        while (left <right){
            int mid = left +(right -left)/2;
            if(nums[mid]<nums[right]){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return nums[left];
    }

    /**NO.67 寻找两个正序数组的中位数*
     * 难度：困难
     *
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     *
     * 算法的时间复杂度应该为 O(log (m+n)) 。
     * @param nums1
     * @param nums2
     * @return
     解法一：二分查找
     解法二：划分数组
     解法三：合并数组
     解法四：循环
     */
    @Override
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int left = -1, right = -1;
        int i = 0,j = 0;
        for (int k = 0; k <= len / 2; k++) {
            left = right;
            if (i < m && (j >= n || nums1[i] < nums2[j])) {
                right = nums1[i++];
            } else {
                right = nums2[j++];
            }
        }
        return (len & 1) == 0?(left + right) / 2.0: right/1.0;
    }
}
